# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        """使用拼接链表，免于用hash，多增加一次循环
        """
        if head is None:
            return None
        
        # 复制拼接链表
        old = head
        while old is not None:
            new = Node(old.val, old.next)
            old.next = new
            old = new.text
        
        # 复制random指针
        old = head
        while old is not None:
            if old.random is not None:
                old.next.random = old.random.next
            old = old.next.next
        
        # 分割新旧链表
        old, res, new = head, head.next, head.next
        while new.next is not None:
            old.next = new.next
            old = old.next
            new.next = old.next
            new = new.next
        old.next = None
        
        return res